class Solution {
    /**
     * 未持有股票       d[i][0]  = d[i-1][0]
     * 未持有股票买过1个 d[i][1]  = max(d[i-1][1], d[i-1][3]+prices[i])
     * 未持有股票买过2个 d[i][2]  = max(d[i-1][2], d[i-1][4]+prices[i])
     * 持有1个股票      d[i][3]  = max(d[i-1][3], d[i-1][0]-prices[i])
     * 持有1个股票且买过 d[i][4]  = max(d[i-1][4], d[i-1][1]-prices[i])
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0)
            return 0;

        int[][] d = new int[len][5];
        d[0][3] = -prices[0];// 第一天买入
        d[0][4] = -prices[0];// 第一天买入卖出再买入

        for (int i = 1; i < len; i++) {
            d[i][0] = d[i - 1][0];
            d[i][1] = Math.max(d[i - 1][1], d[i - 1][3] + prices[i]);
            d[i][2] = Math.max(d[i - 1][2], d[i - 1][4] + prices[i]);
            d[i][3] = Math.max(d[i - 1][3], d[i - 1][0] - prices[i]);
            d[i][4] = Math.max(d[i - 1][4], d[i - 1][1] - prices[i]);
        }
        return Math.max(d[len - 1][1], d[len - 1][2]);
    }

}
